#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>

 struct ListNode {
    int val;
    struct ListNode* next;
};

 struct ListNode* ReverseList(struct ListNode* head) {
     // write code here
     struct ListNode* rem = NULL;
     while (head != NULL)
     {
         struct ListNode* rem2 = head->next;
         head->next = rem;
         rem = head;
         head = rem2;
     }
     return rem;
 }
 bool chkPalindrome(struct ListNode* A) {
     if (A->next == NULL) return true;
     // write code here
     struct ListNode* fast = A;
     struct ListNode* slow = A;
     while (fast->next != NULL && fast->next->next != NULL)
     {
         slow = slow->next;
         fast = fast->next->next;
     }
     struct ListNode* rem = slow->next;
     struct ListNode* rem2 = fast->next;
     slow->next = NULL;
     struct ListNode* B = ReverseList(rem);
     rem->next = NULL;
     if (rem2 == NULL)
     {
         rem->next = slow;
     }
     while (A != NULL && B != NULL)
     {
         if (A->val != B->val) return false;
         A = A->next;
         B = B->next;
     }
     if (A == NULL && B == NULL) return true;
     return false;
 }

 int main()
 {
     struct ListNode a1 = { 1,NULL };
     struct ListNode a2 = { 2,NULL };
     struct ListNode a3 = { 2,NULL };
     struct ListNode a4 = { 1,NULL };
     bool flag = chkPalindrome(&a1);
     return 0;
 }